package algorithm.poj.p3000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;
import java.util.Arrays;


/**
 * 分析：
 * 
 * 实现：
 * 
 * 经验和教训：
 * 
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P3292 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P3292.class.getResource("P3292.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

		int[] hps = hPrimes((1000001-1)/4);
		int[] hsps = hSemiPrimes((1000001-1)/4, hps);
		String line = stdin.readLine();
		while (line != null && !"0".equals(line.trim())) {
			int p = Integer.valueOf(line.trim());
			int index = Arrays.binarySearch(hsps, p);
			if (index >= 0) {
				System.out.println(p + " " + (index+1));
			} else {
				System.out.println(p + " " + (-index-1));
			}
			line = stdin.readLine();
		}
	}
	
	/**
	 * return all H-Semi-primes less than 4m+1 
	 * @param m
	 * @return
	 */
	private static int[] hSemiPrimes(int m, int[] hps) {
		
		int[] tmp = new int[m];
		int count = 0;
		for (int i = 0; i < m; i ++) {
			int hsp = 4*i+1;
			for (int j = 0; j < hps.length && j <= i && hps[j]*hps[j] <= hsp; j ++) {
				if (hsp%hps[j] == 0) {
					int b = hsp/hps[j];
					if (Arrays.binarySearch(hps, b) > -1) {
						tmp[i] = 1;
						count ++;
						break;
					}
				}
			}
		}
		
		int index = 0;
		int[] hsps = new int[count];
		for (int i = 0; i < m; i ++) {
			if (tmp[i] != 0) {
				hsps[index ++] = 4*i+1;
			}
		}

		return hsps;
	}


	/**
	 * return all H-primes less than 4m+1 
	 * @param m
	 * @return
	 */
	private static int[] hPrimes(int m) {
		
		if (m <= 1) {
			return new int[0];
		} else if (m == 2) {
			return new int[] {5};
		} else {
			int count = 0;
			int[] ns = new int[m];
			for (int i = 0; i < m; i ++) ns[i] = i;
			ns[0] = 0;
			ns[1] = 1;
			
			int index = 1;
			int p = 0;
			while (index < m) {
				if (ns[index] != 0) {
					count ++;
					p = 4*index+1;
					for (int j = index+p; j < m; j += p) {
						ns[j] = 0;
					}
				}
				index ++;
			}
			
			index = 0;
			int[] ps = new int[count];
			for (int i = 0; i < m; i ++) {
				if (ns[i] != 0) {
					ps[index ++] = 4*i+1;
				}
			}

			return ps;
		}
	}
}